package j2024.j202409;

import java.util.ArrayList;

public class j0905 {
    /**
     * 376. 摆动序列
     * @param nums
     * @return
     */
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if(n<2){
            return n;
        }
        int ret = 0,left = 0;
        for (int i = 0; i < n-1; i++) {
            int right = nums[i+1]-nums[i];//计算接下来的趋势
            if(right==0){
                continue;
            }
            if(left * right<=0){
                ret++;
            }
            left = right;
        }
        return  ret+1;
    }


    /**
     * 300. 最长递增子序列
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        ArrayList<Integer> ret = new ArrayList<>();
        int n = nums.length;
        ret.add(nums[0]);
        for (int i = 1; i < n; i++) {
            if(nums[i]>ret.get(ret.size()-1)){
                ret.add(nums[i]);
            }else {
                int left = 0,right = ret.size()-1;
                while(left<right){
                    int mid = (left+right)/2;
                    if(ret.get(mid)<nums[i]){
                        left = mid+1;
                    }else {
                        right = mid;
                    }
                }
                ret.set(left,nums[i]);
            }
        }
        return ret.size();
    }
}
